|
In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither ''K''5 (the complete graph on five vertices) nor ''K''3,3 (the utility graph, a complete bipartite graph on six vertices). This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem. ==Definitions and theorem statement== A planar embedding of a given graph is a drawing of the graph in the Euclidean plane, with points for its vertices and curves for its edges, in such a way that the only intersections between pairs of edges are at a common endpoint of the two edges. A minor of a given graph is another graph formed by deleting vertices, deleting edges, and contracting edges. When an edge is contracted, its two endpoints are merged to form a single vertex. In some versions of graph minor theory the graph resulting from a contraction is simplified by removing self-loops and multiple adjacencies, while in other version multigraphs are allowed, but this variation makes no difference to Wagner's theorem. Wagner's theorem states that every graph has either a planar embedding, or a minor of one of two types, the complete graph ''K''5 or the complete bipartite graph ''K''3,3. (It is also possible for a single graph to have both types of minor.) If a given graph is planar, so are all its minors: vertex and edge deletion obviously preserve planarity, and edge contraction can also be done in a planarity-preserving way, by leaving one of the two endpoints of the contracted edge in place and routing all of the edges that were incident to the other endpoint along the path of the contracted edge. A ''minor-minimal'' non-planar graph is a graph that is not planar, but in which all proper minors (minors formed by at least one deletion or contraction) are planar. Another way of stating Wagner's theorem is that there are only two minor-minimal non-planar graphs, ''K''5 and ''K''3,3. Another result also sometimes known as Wagner's theorem states that a four-connected graph is planar if and only if it has no ''K''5 minor. That is, by assuming a higher level of connectivity, the graph ''K''3,3 can be made unnecessary in the characterization, leaving only a single forbidden minor, ''K''5. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Wagner's theorem」の詳細全文を読む スポンサード リンク
|